#include <iostream>
#include <random>
using namespace std;
class Solution
{
public:
    long long gcd(long long a, long long b)
    {
        if (b == 0)
        {
            return a;
        }
        return gcd(b, a % b);
    }
    long long lcm(long long a, long long b)
    {
        return a / gcd(a,b) * b;
    }
    int nthMagicalNumber(int n, int a, int b)
    {
        long long left = 0;
        long long  lcm = this->lcm(a,b); // 求解最小公倍数
        long long tmp = n;
        long long right = tmp * min(a,b);
        long long ans = 0; //坑，这里的ans会溢出 use long long  not int
        while (left <= right)
        {
            long long mid = (left + right)/2;
            cout<<"mid:"<<mid<<endl;
            if ((mid/a + mid / b - mid/lcm) >= n)
            {
                ans = mid;
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }
        return (ans)%1000000007;
    }
};
long long optimizedBruteForce(int n, int a, int b) {
    // 特殊情况：a和b相等时，直接返回n*a（避免重复计算）
    if (a == b) {
        return ( (long long)n * a ) % 1000000007;
    }
    
    long long i = 1, j = 1; // 指针：i对应a的倍数序号，j对应b的倍数序号
    int count = 0;          // 已找到的神奇数数量
    long long result = 0;   // 第n个神奇数
    
    while (count < n) {
        long long numA = i * a; // 当前a的倍数
        long long numB = j * b; // 当前b的倍数
        
        if (numA < numB) {
            // 取a的倍数，移动a的指针
            result = numA;
            i++;
        } else if (numB < numA) {
            // 取b的倍数，移动b的指针
            result = numB;
            j++;
        } else {
            // 两数相等（公倍数），只算一次，同时移动两个指针
            result = numA;
            i++;
            j++;
        }
        count++;
    }
    
    return result % 1000000007;
}

void testLogger() {
    // 随机数生成器（确保覆盖多种情况）
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dist_n(1, 1000000);    // n的范围：1~10000（避免暴力法过慢）
    uniform_int_distribution<> dist_ab(1, 1000);    // a、b的范围：1~1000

    const int testTimes = 1; // 测试次数
    Solution sol;

    for (int t = 0; t < testTimes; t++) {
        int n = 1000000;//dist_n(gen);
        int a = 4000;//dist_ab(gen);
        int b = 4000;//dist_ab(gen);

        // 计算两个方法的结果
        long long res_binary = sol.nthMagicalNumber(n, a, b);
        long long res_brute = optimizedBruteForce(n, a, b);

        if (res_binary != res_brute) {
            // 输出错误用例
            cout << "❌ 测试用例失败！" << endl;
            cout << "n = " << n << ", a = " << a << ", b = " << b << endl;
            cout << "二分法结果: " << res_binary << endl;
            cout << "暴力法结果: " << res_brute << endl;
            return; // 发现错误即停止
        }
    }

    cout << "✅ 所有 " << testTimes << " 个测试用例均通过！" << endl;
}
int main(int argc, char const *argv[])
{
    /* code */
    testLogger();
    return 0;
}
